{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximal Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximalSquare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大正方形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个由 <code>'0'</code> 和 <code>'1'</code> 组成的二维矩阵内，找到只包含 <code>'1'</code> 的最大正方形，并返回其面积。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg\" style=\"width: 400px; height: 319px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg\" style=\"width: 165px; height: 165px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[\"0\",\"1\"],[\"1\",\"0\"]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[\"0\"]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 300</code></li>\n",
    "\t<li><code>matrix[i][j]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximal-square](https://leetcode.cn/problems/maximal-square/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximal-square](https://leetcode.cn/problems/maximal-square/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]', '[[\"0\",\"1\"],[\"1\",\"0\"]]', '[[\"0\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        # edge cases\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        \n",
    "         \n",
    "        \n",
    "        # initialize the dp values\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        \n",
    "        # initialize the variable to track the max area when loop through the matrix\n",
    "        \n",
    "        max_area = 0\n",
    "        \n",
    "        dp = [[0]*col for _ in range(row)]\n",
    "        \n",
    "        for c in range(col):\n",
    "            dp[0][c] = int(matrix[0][c])\n",
    "            max_area = max(max_area,dp[0][c])\n",
    "        for r in range(row):\n",
    "            dp[r][0] = int(matrix[r][0])\n",
    "            max_area = max(max_area,dp[r][0])\n",
    "       \n",
    "        \n",
    "        # loop through the matrix and record the result into dp matrix\n",
    "        \n",
    "        for r in range(1,row):\n",
    "            for c in range(1,col):\n",
    "                if matrix[r][c] == \"1\":\n",
    "                    dp[r][c] = min(dp[r-1][c],dp[r][c-1],dp[r-1][c-1]) + 1\n",
    "                    max_area = max(max_area,dp[r][c]*dp[r][c])\n",
    "        \n",
    "        return max_area\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not matrix: return 0\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        board = [[0 for _ in range(col + 1)] for _ in range(row + 1)]\n",
    "        res = 0\n",
    "        for i in range(1, row + 1):\n",
    "            for j in range(1, col + 1):\n",
    "                if matrix[i - 1][j - 1] == \"1\":\n",
    "                    left = board[i - 1][j]\n",
    "                    up = board[i][j - 1]\n",
    "                    dia = board[i - 1][j - 1]\n",
    "                    board[i][j] += 1 + min(left, up, dia)\n",
    "                    res = max(res, board[i][j])\n",
    "        return res**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # matrix = [[\"1\"],[\"0\"],[\"1\"],[\"1\"],[\"1\"],[\"1\"],[\"0\"]]\n",
    "        if len(matrix) is 0:\n",
    "            return 0\n",
    "        if len(matrix) is 1:\n",
    "            for i in matrix[0]:\n",
    "                if i == \"1\":\n",
    "                    return 1\n",
    "            return 0\n",
    "        if len(matrix)>1 and len(matrix[0])==1:\n",
    "            for i in matrix:\n",
    "                if i[0] == \"1\":\n",
    "                    return 1\n",
    "            return 0\n",
    "        dp = [[int(i) for i in c] for c in matrix]\n",
    "        self.m = max(dp[0][0],dp[0][1],dp[1][0],dp[1][1])\n",
    "        l, h = len(matrix[0]), len(matrix)\n",
    "        if l>h:\n",
    "            s = '1>2'\n",
    "        elif l<h:\n",
    "            s = '2>1'\n",
    "        else:\n",
    "            s = '1=2'\n",
    "        le= min(l,h)\n",
    "        def handle_1(le_1,dp):\n",
    "            for i in range(1,le_1):\n",
    "                for j in range(1,i):\n",
    "                    if dp[j][i]:\n",
    "                        dp[j][i] = min(dp[j-1][i-1],dp[j-1][i],dp[j][i-1]) + 1\n",
    "                        if dp[j][i]>self.m:\n",
    "                            self.m = dp[j][i]\n",
    "                for j in range(1,i):\n",
    "                    if dp[i][j]:\n",
    "                        dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + 1\n",
    "                        if dp[i][j]>self.m:\n",
    "                            self.m = dp[i][j]\n",
    "                if dp[i][i]:\n",
    "                    dp[i][i] = min(dp[i-1][i-1],dp[i][i-1],dp[i-1][i]) + 1\n",
    "                    if dp[i][i]>self.m:\n",
    "                        self.m = dp[i][i]\n",
    "        def handle_2(l,h,s,dp):\n",
    "            if s == '1>2':\n",
    "                for i in range(1,h):\n",
    "                    for j in range(h,l):\n",
    "                        if dp[i][j]:\n",
    "                            dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + 1\n",
    "                            if dp[i][j]>self.m:\n",
    "                                self.m = dp[i][j]\n",
    "                \n",
    "            elif s == '2>1':\n",
    "                for i in range(1,l):\n",
    "                    for j in range(l,h):\n",
    "                        if dp[j][i]:\n",
    "                            dp[j][i] = min(dp[j-1][i-1],dp[j-1][i],dp[j][i-1]) + 1\n",
    "                            if dp[j][i]>self.m:\n",
    "                                self.m = dp[j][i]\n",
    "            else:\n",
    "                pass\n",
    "        handle_1(le,dp)\n",
    "        handle_2(l,h,s,dp)\n",
    "        \n",
    "        \n",
    "        return self.m**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def maximalSquare(self, matrix):\n",
    "            \"\"\"\n",
    "            :type matrix: List[List[str]]\n",
    "            :rtype: int\n",
    "            \"\"\"\n",
    "            if len(matrix) == 0:\n",
    "                return 0\n",
    "            dp = [[int(i) for i in c] for c in matrix]\n",
    "            visit = [[False for _ in c] for c in matrix]\n",
    "            self.max = 0\n",
    "\n",
    "            def BFS(dp):\n",
    "                queue = [[0, 0]]\n",
    "                d = [[1, 0], [0, 1]]\n",
    "                while len(queue) > 0:\n",
    "                    node = queue.pop()\n",
    "                    visit[0][0] = True\n",
    "                    if node[0] - 1 >= 0 and node[1] - 1 >= 0:\n",
    "                        if dp[node[0]][node[1]]:\n",
    "                            dp[node[0]][node[1]] = min(dp[node[0] - 1][node[1]], dp[node[0]][node[1] - 1],\n",
    "                                                       dp[node[0] - 1][node[1] - 1]) + 1\n",
    "                    else:\n",
    "                        pass\n",
    "\n",
    "                    if dp[node[0]][node[1]] > self.max:\n",
    "                        self.max = dp[node[0]][node[1]]\n",
    "\n",
    "                    for n in d:\n",
    "                        if node[0] + n[0] < len(matrix) and node[1] + n[1] < len(matrix[0]):\n",
    "                            if visit[node[0] + n[0]][node[1] + n[1]] == False:\n",
    "                                queue.insert(0, [node[0] + n[0], node[1] + n[1]])\n",
    "                                visit[node[0] + n[0]][node[1] + n[1]] = True\n",
    "\n",
    "\n",
    "            BFS(dp)\n",
    "\n",
    "            return self.max ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        #res用于保存矩阵中最大正方形的边长\n",
    "        res = 0\n",
    "        \n",
    "        #dp数组用于记录每一个位置能够取到的正方形的最大边长\n",
    "        dp = [[0 for i in range(n)] for j in range(m)]\n",
    "        \n",
    "        #矩阵最左侧一列如果存在为1的元素，那么该位置的最大正方形边长就是1\n",
    "        #更新整个矩阵的最大正方形边长res\n",
    "        for i in range(0,m):\n",
    "            if matrix[i][0] == '1':\n",
    "                dp[i][0] = 1\n",
    "                res = 1\n",
    "                \n",
    "        #矩阵最上侧一行如果存在为1的元素，那么该位置的最大正方形边长就是1\n",
    "        #更新整个矩阵的最大正方形边长res\n",
    "        for j in range(0,n):\n",
    "            if matrix[0][j] == '1':\n",
    "                dp[0][j] = 1\n",
    "                res = 1\n",
    "                \n",
    "        #遍历整个矩阵，更新dp数组和res的值\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                #在每个元素的位置都要比较和更新dp数组和res的值\n",
    "                if matrix[i][j] == '1':\n",
    "                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1\n",
    "                    \n",
    "                res = max(res,dp[i][j])\n",
    "        \n",
    "        return res*res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        row = self.matrix_acc(matrix)\n",
    "        col = self.matrix_acc(list(zip(*matrix)))\n",
    "        col = list(map(list, zip(*col)))\n",
    "        #show_2d_array(row)\n",
    "        #show_2d_array(col)\n",
    "        \n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            if matrix[i][0] == \"1\":\n",
    "                dp[i][0] = 1\n",
    "        for j in range(n):\n",
    "            if matrix[0][j] == \"1\":\n",
    "                dp[0][j] = 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    dp[i][j] = min(row[i-1][j], col[i][j-1], dp[i-1][j-1]) + 1\n",
    "                    \n",
    "        #show_2d_array(dp)\n",
    "        rtv = max(map(max, zip(*dp))) ** 2\n",
    "        return rtv\n",
    "                \n",
    "        \n",
    "    def matrix_acc(self, matrix):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        \n",
    "        row = [[0]*n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            row[0][j] = 0 if matrix[0][j] == '0' else 1\n",
    "            \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    row[i][j] = row[i-1][j] + 1  \n",
    "                else:\n",
    "                    row[i][j] = 0\n",
    "        \n",
    "        return row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        xlen = len(matrix)\n",
    "        if xlen == 0:\n",
    "            return 0\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, num in enumerate(row):\n",
    "                if i == 0 or j == 0:\n",
    "                    if(int(row[j]) > result):\n",
    "                        result = int(row[j])\n",
    "                    continue\n",
    "                if row[j] == '0':\n",
    "                    continue\n",
    "                left = int(row[j - 1])\n",
    "                up = int(matrix[i - 1][j])\n",
    "                left_up = int(matrix[i - 1][j - 1])\n",
    "                if left == 0 or up == 0 or left_up == 0:\n",
    "                    continue\n",
    "                row[j] = str(int(row[j]) + min(left, up, left_up))\n",
    "                if int(row[j]) > result:\n",
    "                    result = int(row[j])\n",
    "        return result * result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        nums = [int(''.join(row), base=2) for row in matrix]\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        \n",
    "        for i in range(n):\n",
    "            j = i\n",
    "            num = nums[i]\n",
    "            while j < n:\n",
    "                num = num & nums[j]\n",
    "                if not num:\n",
    "                    break\n",
    "                l = 0\n",
    "                curnum = num\n",
    "                while curnum:\n",
    "                    l += 1\n",
    "                    curnum &= curnum << 1\n",
    "                l = min(l, j - i + 1)\n",
    "                ans = max(ans, l * l)\n",
    "                j += 1\n",
    "        return ans\n",
    "    \n",
    "[[\"1\",\"0\",\"1\",\"1\",\"1\"],\n",
    " [\"0\",\"1\",\"0\",\"1\",\"0\"],\n",
    " [\"1\",\"1\",\"0\",\"1\",\"1\"],\n",
    " [\"1\",\"1\",\"0\",\"1\",\"1\"],\n",
    " [\"0\",\"1\",\"1\",\"1\",\"1\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(matrix)==0:\n",
    "            return 0\n",
    "        lists=[[0 for i in matrix[0]] for j in matrix]\n",
    "        lists[0]=matrix[0]\n",
    "        maxnum=0\n",
    "        if '1' in matrix[0]:\n",
    "            maxnum=1\n",
    "        for i in range(len(matrix)):\n",
    "            if matrix[i][0]=='1':\n",
    "                maxnum=1\n",
    "        for i in range(len(matrix)):\n",
    "            lists[i][0]=matrix[i][0]\n",
    "        for i in range(1,len(matrix)):\n",
    "            for j in range(1,len(matrix[0])):\n",
    "                if matrix[i][j]=='0':\n",
    "                    lists[i][j]='0'\n",
    "                else:\n",
    "                    if lists[i][j-1]!=lists[i-1][j]:\n",
    "                        lists[i][j]=str(min(int(lists[i][j-1]),int(lists[i-1][j]))+1)\n",
    "                        maxnum=max(maxnum,int(lists[i][j]))\n",
    "                    else:\n",
    "                        if matrix[i-int(lists[i-1][j])][j-int(lists[i-1][j])]=='1':\n",
    "                            lists[i][j]=str(int(lists[i-1][j])+1)\n",
    "                            maxnum=max(maxnum,int(lists[i][j]))\n",
    "                        else:\n",
    "                            lists[i][j]=lists[i-1][j]\n",
    "                            maxnum=max(maxnum,int(lists[i][j]))\n",
    "        return maxnum**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        #矩阵的行和列\n",
    "        rows,cols=len(matrix),len(matrix[0])\n",
    "        maxlen,prev=0,0\n",
    "        dp=[0]*(cols+1)\n",
    "        for i in range(1,rows+1):\n",
    "            for j in range(1,cols+1):\n",
    "                #提前保存左斜上角的元素\n",
    "                tmp=dp[j]\n",
    "                if matrix[i-1][j-1]=='1':\n",
    "                    #其中dp[j-1]对应dp[i][j-1],dp[j]对应dp[i-1][j],prev对应dp[i-1][j-1],左斜上角的元素\n",
    "                    dp[j]=min(min(dp[j-1],prev),dp[j])+1\n",
    "                    maxlen=max(maxlen,dp[j])\n",
    "                else:\n",
    "                    dp[j]=0\n",
    "                #当dp[j]改变的时候\n",
    "                prev=tmp\n",
    "        return maxlen*maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0]) if m > 0 else 0\n",
    "        dp = [0]*(n+1)\n",
    "        maxlen = 0\n",
    "        prev = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                temp = dp[j]\n",
    "                if matrix[i-1][j-1] =='1':\n",
    "                    dp[j] = min(min(prev, dp[j-1]), dp[j])+1\n",
    "                    maxlen = max(maxlen, dp[j])\n",
    "                else:\n",
    "                    dp[j] = 0\n",
    "                prev = temp\n",
    "        return maxlen*maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        if row == 1:\n",
    "            for i in range(col):\n",
    "                if matrix[0][i] == '1':\n",
    "                    return 1\n",
    "            return 0\n",
    "        if col == 1:\n",
    "            for i in range(row):\n",
    "                if matrix[i][0] == '1':\n",
    "                    return 1\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j] == '1':\n",
    "                    matrix[i][j] = 1\n",
    "                else:\n",
    "                    matrix[i][j] = 0\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j]:\n",
    "                    if i != 0 and j != 0:\n",
    "                        a, b, c = matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]\n",
    "                        matrix[i][j] = min(a, b, c) + 1\n",
    "                    res = max(res, matrix[i][j])\n",
    "        return res ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix and not matrix[0]:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]\n",
    "\n",
    "        result = 0\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            dp[i][0] = int(matrix[i][0])\n",
    "            result = max(dp[i][0], result)\n",
    "\n",
    "        for j in range(len(matrix[0])):\n",
    "            dp[0][j] = int(matrix[0][j])\n",
    "            result = max(dp[0][j], result)\n",
    "\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if matrix[i][j] == '0':\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1\n",
    "                    result = max(dp[i][j], result)\n",
    "\n",
    "        return result * result\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        dp = [[0]*cols for _ in range(rows)]\n",
    "        ans = 0\n",
    "        for i in range(cols):\n",
    "            dp[0][i] = int(matrix[0][i])\n",
    "            if dp[0][i]: ans = 1\n",
    "        for i in range(rows):\n",
    "            dp[i][0] = int(matrix[i][0])\n",
    "            if dp[i][0]: ans = 1\n",
    "        for i in range(1, rows):\n",
    "            for j in range(1, cols):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    mins = min(dp[i-1][j], dp[i][j-1])\n",
    "                    mins = min(mins, dp[i-1][j-1])\n",
    "                    dp[i][j] = mins + 1\n",
    "\n",
    "                ans = max(ans, dp[i][j])\n",
    "\n",
    "        return ans**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = None\n",
    "        self.row_num = 0\n",
    "        self.col_num = 0\n",
    "        self.direction = [[0, 1], [1, 1], [1, 0]] # 右，斜，下\n",
    "\n",
    "    def maximalSquare(self, matrix):\n",
    "        self.row_num = len(matrix)\n",
    "        self.col_num = len(matrix[0])\n",
    "\n",
    "        self.visited = [[-1 for _ in range(self.col_num)] for _ in range(self.row_num)]\n",
    "        re = [0]\n",
    "        for i in range(self.row_num):\n",
    "            for j in range(self.col_num):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    if self.visited[i][j] == -1:\n",
    "                        re.append(self.__max_square(matrix, i, j))\n",
    "                    else:\n",
    "                        re.append(self.visited[i][j])\n",
    "\n",
    "        max_re = max(re)\n",
    "        return max_re * max_re\n",
    "\n",
    "\n",
    "    def __max_square(self, matrix, start_i, start_j):\n",
    "\n",
    "        if start_i == self.row_num-1 or start_j == self.col_num-1:\n",
    "            self.visited[start_i][start_j] = 1\n",
    "            return 1\n",
    "\n",
    "        re = []\n",
    "        for dir in self.direction:\n",
    "            new_start_i = start_i + dir[0]\n",
    "            new_start_j = start_j + dir[1]\n",
    "            if matrix[new_start_i][new_start_j] == \"1\":\n",
    "                if self.visited[new_start_i][new_start_j] != -1:\n",
    "                    re.append(1 + self.visited[new_start_i][new_start_j])\n",
    "                else:\n",
    "                    re.append(1 + self.__max_square(matrix, new_start_i, new_start_j))\n",
    "            else:\n",
    "                re.append(1)\n",
    "                break\n",
    "        min_re = min(re)\n",
    "        self.visited[start_i][start_j] = min_re\n",
    "        return min_re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "dp max square with right bottom node i, j\n",
    "\n",
    "dp = (min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) ^ 0.5 + 1) ^ 2\n",
    "\n",
    "base case\n",
    "padding\n",
    "if ij = 0, dp = 0\n",
    "\n",
    "'''\n",
    "import math\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix) -> int:\n",
    "        # corner case\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "\n",
    "        # dp\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        res = 0\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if matrix[i - 1][j - 1] == \"1\":\n",
    "                        dp[i][j] = ((min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])) ** 0.5 + 1) ** 2\n",
    "                    else:\n",
    "                        dp[i][j] = 0\n",
    "                res = max(res, dp[i][j])\n",
    "        return int(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == '0':\n",
    "                    continue\n",
    "                else:\n",
    "                    ans = max(ans, 1)\n",
    "                if i == 0 or j == 0:\n",
    "                    continue\n",
    "                if int(matrix[i-1][j])>=1 and int(matrix[i-1][j-1])>=1 and int(matrix[i][j-1])>=1:\n",
    "                    matrix[i][j] = min(int(matrix[i-1][j]),int(matrix[i-1][j-1]),int(matrix[i][j-1]))+1\n",
    "                    ans = max(ans, matrix[i][j])\n",
    "                    matrix[i][j] = str(matrix[i][j])\n",
    "\n",
    "        return ans*ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                f[i + 1][j + 1] = int(matrix[i][j]) + f[i][j + 1] + f[i + 1][j] - f[i][j]\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)] \n",
    "        #dp[i][j] = The largest square containing only 1's up till coordinates (i, j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    if int(matrix[i][j]) == 1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        if j == 0:\n",
    "                            dp[i][j] = dp[i - 1][j]\n",
    "\n",
    "                        else:\n",
    "                            dp[i][j] = dp[i][j - 1]\n",
    "\n",
    "                else:\n",
    "                    if int(matrix[i][j]) == 0 or dp[i - 1][j] != dp[i][j - 1]:\n",
    "                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "\n",
    "                    else:\n",
    "                        size = dp[i - 1][j] #i, j = 2, 3, size = 1\n",
    "                        if f[i + 1][j + 1] - f[i + 1][j - size] - f[i - size][j + 1] + f[i - size][j - size] == (size + 1) ** 2:\n",
    "                            dp[i][j] = size + 1\n",
    "                        else:\n",
    "                            dp[i][j] = size\n",
    "    \n",
    "        return dp[m - 1][n - 1] ** 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        matrix = [[int(c) for c in row] for row in matrix]\n",
    "        dp = [[0]*cols for _ in range(rows)]\n",
    "        memo = dict()\n",
    "\n",
    "        def max_extending_square(r, c, expect):\n",
    "            if memo.get((r, c, expect)):\n",
    "                return memo[(r,c,expect)]\n",
    "            if not expect:\n",
    "                return True\n",
    "            if r+1 < expect or c+1 < expect:\n",
    "                return False\n",
    "            for i in range(r, r-expect, -1):\n",
    "                if not matrix[i][c]:\n",
    "                    return False\n",
    "            for j in range(c, c-expect, -1):\n",
    "                if not matrix[r][j]:\n",
    "                    return False\n",
    "            memo[(r,c,expect)] = max_extending_square(r-1, c-1, expect-1)\n",
    "            return memo[(r,c,expect)]\n",
    "\n",
    "        for i, num in enumerate(matrix[0]):\n",
    "            dp[0][i] = num\n",
    "        for j in range(rows):\n",
    "            dp[j][0] = matrix[j][0]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, col in enumerate(row):\n",
    "                if i > 0 and j > 0:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "                    if max_extending_square(i, j, dp[i][j]+1):\n",
    "                        dp[i][j] += 1\n",
    "                    continue\n",
    "                if i > 0:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j])\n",
    "                if j > 0:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i][j])\n",
    "        return dp[-1][-1]**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        stack = [(i, j, 1) for i in range(m) for j in range(n) if matrix[i][j] == '1']\n",
    "        max_area = 0 if len(stack) == 0 else 1\n",
    "        while stack:\n",
    "            i, j, side = stack.pop()\n",
    "            if side**2 > max_area:\n",
    "                max_area = side**2\n",
    "            flag = 1\n",
    "            print(i, j, side)\n",
    "            for s in range(side):\n",
    "                if i+1 > m-1 or j+1 > n-1 or i-s < 0 or j-s < 0:\n",
    "                    flag = 0\n",
    "                    break\n",
    "                if matrix[i+1][j] != '1' or matrix[i+1][j-s] != '1' or matrix[i][j+1] != '1' or matrix[i-s][j+1] != '1' or matrix[i+1][j+1] != '1':\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:\n",
    "                stack.append((i+1, j+1, side+1))\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        \n",
    "        if len(matrix) == 1:\n",
    "            if '1' in matrix[0]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "            \n",
    "        dp = [[i, j] for i in range(len(matrix)) for j in range(len(matrix[0])) if matrix[i][j] == '1']\n",
    "        if len(dp) == 0:\n",
    "            return 0\n",
    "        for i in range(1, min(len(matrix), len(matrix[0])) + 1):\n",
    "            # print(i)\n",
    "            new_dp = []\n",
    "            for j in dp:\n",
    "                if j[0] + i >= len(matrix) or j[1] + i >= len(matrix[0]):\n",
    "                    continue\n",
    "                status = True\n",
    "                for x in range(i + 1):\n",
    "                    if matrix[j[0] + i][j[1] + x] != '1':\n",
    "                        status = False\n",
    "                        break\n",
    "                for y in range(i + 1):\n",
    "                    if matrix[j[0] + y][j[1] + i] != '1':\n",
    "                        status = False\n",
    "                        break\n",
    "                if status:\n",
    "                    new_dp.append(j)\n",
    "            dp = new_dp\n",
    "            if len(dp) == 0:\n",
    "                break\n",
    "            # print(dp)\n",
    "        return i ** 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        maxEdge = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                if i and j:\n",
    "                    if matrix[i][j]==\"1\":\n",
    "                        matrix[i][j]=min(int(matrix[i-1][j-1]),int(matrix[i][j-1]),int(matrix[i-1][j]))+1\n",
    "                    else:\n",
    "                        matrix[i][j]=0\n",
    "                maxEdge = max(maxEdge,int(matrix[i][j]))\n",
    "        return maxEdge**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        M = len(matrix)\n",
    "        N = len(matrix[0])\n",
    "        dp = [ [0] * N for _ in range(M)]\n",
    "        max_num=0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "        for i in range(M):\n",
    "            dp[i][0] = matrix[i][0]\n",
    "        for j in range(N):\n",
    "            dp[0][j] = matrix[0][j]\n",
    "        for i in range(1,M):\n",
    "            for j in range(1,N):\n",
    "                if(matrix[i][j]==1):\n",
    "                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                    max_num = max(max_num,dp[i][j])\n",
    "        return max_num**2 \n",
    "        # return max(map(max,dp)) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        \n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "\n",
    "        # 最大边长\n",
    "        max_side = int(matrix[0][0])\n",
    "        for i in range(0, rows):\n",
    "            for j in range(0, columns):\n",
    "                if int(matrix[i][j]) == 1 and i != 0 and j != 0:\n",
    "                    # dp递推式\n",
    "                    matrix[i][j] = min(int(matrix[i - 1][j - 1]), int(matrix[i - 1][j]), int(matrix[i][j - 1])) + 1\n",
    "\n",
    "                max_side = max(max_side, int(matrix[i][j]))\n",
    "        \n",
    "        return max_side * max_side"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:              \n",
    "        def rec2seq(x1,y1, x2, y2):\n",
    "            return min(abs(x2-x1), abs(y2-y1)) + 1\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    if i > 0 and j > 0:\n",
    "                        a = int(matrix[i-1][j-1])\n",
    "                        b = int(matrix[i-1][j])\n",
    "                        c = int(matrix[i][j-1])\n",
    "                        matrix[i][j] = min(a, b, c) + 1\n",
    "                    else:\n",
    "                        matrix[i][j] = 1    \n",
    "                    res = max(res, matrix[i][j])\n",
    "                    \n",
    "        print(matrix)            \n",
    "        return res*res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        flag = True\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if int(matrix[i][j]) > 0:\n",
    "                    flag = False\n",
    "                if j==0:\n",
    "                    matrix[i][j] = int(matrix[i][j])\n",
    "                    if i > 0:\n",
    "                        matrix[i][j] += matrix[i-1][j]\n",
    "                    continue\n",
    "                \n",
    "                matrix[i][j] = int(matrix[i][j])+ matrix[i][j-1]\n",
    "                if i > 0:\n",
    "                    matrix[i][j] += matrix[i-1][j]\n",
    "                if i > 0 and j >0:\n",
    "                    matrix[i][j] -= matrix[i-1][j-1]\n",
    "        if flag:\n",
    "            return 0\n",
    "        # print(matrix)\n",
    "        res = 1\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                s = 1\n",
    "                while i+s < len(matrix) and j+s < len(matrix[0]):\n",
    "                    t = 0\n",
    "                    if i >0 and j>0:\n",
    "                        t-=matrix[i-1][j-1]\n",
    "                    if i >0:\n",
    "                        t+=matrix[i-1][j+s]\n",
    "                    if j>0:\n",
    "                        t+=matrix[i+s][j-1]\n",
    "\n",
    "                    if matrix[i+s][j+s] - t == ((s+1)**2) :\n",
    "                        # print(i,j,s)\n",
    "                        res = max(res,(s+1)**2)\n",
    "                    s+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        out=0\n",
    "        for x in range(0,len(matrix)):\n",
    "            for y in range(0,len(matrix[0])):\n",
    "                out=max(int(matrix[x][y]),out)\n",
    "                if x!=0 and y!=0 and matrix[x][y]=='1':\n",
    "                    if matrix[x-1][y]!='0' and matrix[x-1][y-1]!='0' and matrix[x][y-1]!='0':\n",
    "                        matrix[x][y]=min(int(matrix[x][y-1]),int(matrix[x-1][y]),int(matrix[x-1][y-1]))+1\n",
    "                    out=int(matrix[x][y]) if int(matrix[x][y])>out else out                   \n",
    "        return out**2\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        \n",
    "        maxSide = 0\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * columns for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                if matrix[i][j] == '1':\n",
    "                    if i == 0 or j == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1\n",
    "                    maxSide = max(maxSide, dp[i][j])\n",
    "        \n",
    "        maxSquare = maxSide * maxSide\n",
    "        return maxSquare\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        row,col = len(matrix),len(matrix[0])\n",
    "        dp = [[0] * col for _ in range(row)]\n",
    "        for j in range(col):\n",
    "            dp[0][j] = int(matrix[0][j])\n",
    "        for i in range(row):\n",
    "            dp[i][0] = int(matrix[i][0])\n",
    "        for i in range(1,row):\n",
    "            for j in range(1,col):\n",
    "                if matrix[i][j] == \"0\":\n",
    "                    dp[i][j] = 0\n",
    "                elif matrix[i][j] == \"1\":\n",
    "                    dp[i][j] = min(int(dp[i-1][j-1]),int(dp[i-1][j]),int(dp[i][j-1])) + int(matrix[i][j])\n",
    "        res = -sys.maxsize\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if dp[i][j] > res:\n",
    "                    res = dp[i][j]\n",
    "        return res * res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "\n",
    "        def f(i, j, length):\n",
    "            # print(i + length, j + length)\n",
    "            if i + length > m - 1 or j + length > n - 1:\n",
    "                return length - 1\n",
    "            for k in range(j, j + length + 1):\n",
    "                if matrix[i + length][k] == '0':\n",
    "                    return length - 1\n",
    "            for k in range(i, i + length + 1):\n",
    "                if matrix[k][j + length] == '0':\n",
    "                    return length - 1\n",
    "            return f(i, j, length + 1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, (f(i, j, 0) + 1) ** 2)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])       \n",
    "        res=0     \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    matrix[i][j]=[0,0] if matrix[i][j]=='0' else [1,1]\n",
    "                    res=max(matrix[i][j][0],res) if matrix[i][j][0]==matrix[i][j][1] else res\n",
    "                elif j==0:\n",
    "                    matrix[i][j]=[0,0] if matrix[i][j]=='0' else [matrix[i-1][j][0]+1,1]\n",
    "                    res=max(matrix[i][j][0],res) if matrix[i][j][0]==matrix[i][j][1] else res\n",
    "                elif i==0:\n",
    "                    matrix[i][j]=[0,0] if matrix[i][j]=='0' else [1,matrix[i][j-1][1]+1]\n",
    "                    res=max(matrix[i][j][0],res) if matrix[i][j][0]==matrix[i][j][1] else res\n",
    "                else:\n",
    "                    # print(i,j,matrix[i][j])\n",
    "                    matrix[i][j]=[0,0] if matrix[i][j]=='0' else [min(matrix[i-1][j-1][0],matrix[i-1][j][0],matrix[i][j-1][0])+1,\n",
    "                    min(matrix[i-1][j-1][1],matrix[i-1][j][1],matrix[i][j-1][1])+1]\n",
    "                    res=max(matrix[i][j][0],res) if matrix[i][j][0]==matrix[i][j][1] else res\n",
    "        print(matrix)\n",
    "\n",
    "        return res*res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        # 高度和宽度\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        # 记录 最大正方向边长 代替记录 最大正方向面积\n",
    "        max_length = 0\n",
    "\n",
    "        # dp[i][j][k] 表示以 i 行第 j 列结尾的最大 1 横向宽度 / 纵向高度 / 正方向边长\n",
    "        dp = [[[0 for _ in range(3)] for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        # 状态转移\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                # 只有当前位置为 '1' 才有进一步计算的必要\n",
    "                if matrix[i-1][j-1] == '1':\n",
    "                    # 1. 计算最大横向宽度 width\n",
    "                    dp[i][j][0] = dp[i][j-1][0] + 1\n",
    "                    # 2. 计算最大纵向高度 height\n",
    "                    dp[i][j][1] = dp[i-1][j][1] + 1\n",
    "                    # 3. 计算当前最大边长\n",
    "                    cur_length = min(dp[i][j][0], dp[i][j][1])\n",
    "                    # 4. 计算最大正方向边长\n",
    "                    dp[i][j][2] = min(dp[i-1][j-1][2] + 1, cur_length)\n",
    "                    # 5. 计算整体最大边长\n",
    "                    max_length = max(max_length, dp[i][j][2])\n",
    "\n",
    "        return max_length ** 2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        max_rectangle = 0\n",
    "        for row in range(len(matrix)):\n",
    "            if matrix[row][0] == \"1\":\n",
    "                max_rectangle = 1\n",
    "                break\n",
    "        if max_rectangle == 0:\n",
    "            for column in range(len(matrix[0])):\n",
    "                if matrix[0][column] == \"1\":\n",
    "                    max_rectangle = 1\n",
    "                    break\n",
    "        for row in range(1,len(matrix)):\n",
    "            for column in range(1,len(matrix[row])):\n",
    "                if matrix[row][column] == \"1\":\n",
    "                    matrix[row][column] = min(int(matrix[row-1][column]),int(matrix[row][column-1]),\\\n",
    "                    int(matrix[row-1][column-1]))+1\n",
    "                if max_rectangle < int(matrix[row][column]) ** 2:\n",
    "                    max_rectangle = int(matrix[row][column]) ** 2\n",
    "        return max_rectangle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        ress = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        ress = 1\n",
    "                else:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        ress = 1\n",
    "                        temp = min(m+1, int(matrix[i][j-1]), int(matrix[i-1][j]), int(matrix[i-1][j-1]))\n",
    "                        if temp >= 1:\n",
    "                            matrix[i][j] = temp + 1\n",
    "                            res = max(res, matrix[i][j])\n",
    "        return max(res * res, ress)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        ress = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        ress = 1\n",
    "                else:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        ress = 1\n",
    "                        temp = min(m+1, int(matrix[i][j-1]), int(matrix[i-1][j]), int(matrix[i-1][j-1]))\n",
    "                        if temp >= 1:\n",
    "                            matrix[i][j] = temp + 1\n",
    "                            res = max(res, matrix[i][j])\n",
    "        return max(res * res, ress)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        pre = [[0, -1], [-1, 0], [-1, -1]]\n",
    "        res = 0\n",
    "        ress = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        ress = 1\n",
    "                else:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        ress = 1\n",
    "                        temp = m + 1\n",
    "                        for l, r in pre:\n",
    "                            temp = min(temp, int(matrix[i+l][j+r]))\n",
    "                        if temp >= 1:\n",
    "                            matrix[i][j] = temp + 1\n",
    "                            res = max(res, matrix[i][j])\n",
    "        return max(res * res, ress)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        rst = 0\n",
    "        for j, c in enumerate(matrix[0]):\n",
    "            matrix[0][j] = int(c)\n",
    "            if matrix[0][j] == 1:\n",
    "                rst = 1\n",
    "        \n",
    "        for i in range(1, len(matrix)):\n",
    "        # 连续的n个>=n就是大小为n的正方形\n",
    "            cnt = [0]*(len(matrix)+1)\n",
    "            for j in range(len(matrix[i])):\n",
    "                matrix[i][j] = 0 if matrix[i][j] == '0' else matrix[i-1][j] + 1\n",
    "                for k in range(len(matrix)+1):\n",
    "                    if k>matrix[i][j]:\n",
    "                        cnt[k] = 0\n",
    "                    else:\n",
    "                        cnt[k] += 1\n",
    "                for k in range(len(matrix)+1):\n",
    "                    if cnt[k] == k:\n",
    "                        rst = max(rst, k)\n",
    "        return rst**2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            matrix[i] = ['0'] + matrix[i]\n",
    "        matrix = [['0' for i in range(n + 1)]] + matrix\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                if matrix[i][j] == '1':\n",
    "                    matrix[i][j] = min(int(matrix[i - 1][j]), int(matrix[i][j - 1]), int(matrix[i - 1][j - 1])) + 1\n",
    "                    res = max(res, matrix[i][j])\n",
    "\n",
    "        return res ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        t = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            str_ = ''\n",
    "            for j in range(t):\n",
    "                str_ += matrix[i][j]\n",
    "            matrix[i] = str_\n",
    "        if '1' in  matrix[0]:\n",
    "            n = 1\n",
    "        else:\n",
    "            n = 0\n",
    "        for i in range(1, m):\n",
    "            a = matrix[i].find('1' * (n + 1))\n",
    "            if a == -1:\n",
    "                continue\n",
    "            while a != -1:\n",
    "                b = 1\n",
    "                for j in range(i - n, i):\n",
    "                    if matrix[2 * i - 1 - n -j][a : a + n + 1] != '1' * (n + 1):\n",
    "                        b = 0\n",
    "                        break\n",
    "                if b == 1:\n",
    "                    n += 1\n",
    "                    break\n",
    "                a = matrix[i].find('1' * (n + 1), a + 1)\n",
    "        return n ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        t = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            str_ = ''\n",
    "            for j in range(t):\n",
    "                str_ += matrix[i][j]\n",
    "            matrix[i] = str_\n",
    "        if '1' in  matrix[0]:\n",
    "            n = 1\n",
    "        else:\n",
    "            n = 0\n",
    "        for i in range(1, m):\n",
    "            a = matrix[i].find('1' * (n + 1))\n",
    "            if a == -1:\n",
    "                continue\n",
    "            while a != -1:\n",
    "                b = 1\n",
    "                for j in range(i - n, i):\n",
    "                    if matrix[j][a : a + n + 1] != '1' * (n + 1):\n",
    "                        b = 0\n",
    "                        break\n",
    "                if b == 1:\n",
    "                    n += 1\n",
    "                    break\n",
    "                a = matrix[i].find('1' * (n + 1), a + 1)\n",
    "        return n ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        lm = len(matrix)\n",
    "        ln = len(matrix[0])\n",
    "        for i in range(lm):\n",
    "            for j in range(ln):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "        max = 0\n",
    "        for i in range(ln):\n",
    "            if matrix[0][i] == 1:\n",
    "                max = 1\n",
    "                break\n",
    "        if not max:\n",
    "            for j in range(lm):\n",
    "                if matrix[j][0] == 1:\n",
    "                    max = 1\n",
    "                    break\n",
    "        for i in range(1,ln):\n",
    "            for j in range(1,lm):\n",
    "                if matrix[j][i]:\n",
    "                    matrix[j][i] = 1 + min(matrix[j-1][i-1],matrix[j-1][i],matrix[j][i-1])\n",
    "                    if matrix[j][i] > max: max = matrix[j][i]\n",
    "        return max * max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        \n",
    "        \n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if matrix[i-1][j-1] == 0: continue\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1\n",
    "\n",
    "        return max([max(dp[i]) for i in range(len(dp))])**2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        height=len(matrix)\n",
    "        width=len(matrix[0])\n",
    "        dp=matrix\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                dp[i][j]=int(dp[i][j])\n",
    "        for i in range(1,height):\n",
    "            for j in range(1,width):\n",
    "                if dp[i][j]!=0:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1\n",
    "        max_value = max(max(row) for row in dp)\n",
    "        print(dp)\n",
    "        return max_value**2\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "       \n",
    "        list(map(lambda x:map(int, x), matrix))\n",
    "        print(matrix)\n",
    "        c = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "                if i == 0:\n",
    "                    if matrix[i][j] != 0:\n",
    "                        if c < matrix[i][j]:\n",
    "                            c = 1\n",
    "                elif j == 0:\n",
    "                    if matrix[i][j] != 0:\n",
    "                        if c < matrix[i][j]:\n",
    "                            c = 1\n",
    "        \n",
    "                elif matrix[i][j] != 0:\n",
    "                    matrix[i][j] = min( int(matrix[i-1][j]),int(matrix[i-1][j-1]),int(matrix[i][j-1])) + matrix[i][j]\n",
    "                    print('if',matrix[i][j])\n",
    "                    if c < matrix[i][j]:\n",
    "                        c = matrix[i][j]\n",
    "\n",
    "\n",
    "        for i in matrix:\n",
    "            print(i)\n",
    "        print(c)\n",
    "        return (c*c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        def func(i, j):\n",
    "            if type(matrix[i][j]) == int:\n",
    "                return matrix[i][j]\n",
    "            if i == len(matrix) - 1 or j == len(matrix[0]) - 1:\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "            elif matrix[i][j] == '1':\n",
    "                matrix[i][j] = min(func(i+1,j), func(i,j+1), func(i+1,j+1)) + 1\n",
    "            else:\n",
    "                matrix[i][j] = 0\n",
    "            return matrix[i][j]\n",
    "        \n",
    "        maxSideLen = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if type(matrix[i][j]) == str:\n",
    "                    maxSideLen = max(maxSideLen, func(i, j))\n",
    "                else:\n",
    "                    maxSideLen = max(maxSideLen, matrix[i][j])\n",
    "        return maxSideLen**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        \n",
    "        \n",
    "        m = len(matrix[0])\n",
    "        n = len(matrix)\n",
    "        #变为01\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "        matrix_copy = [row[:] for row in matrix]\n",
    "        #找边最小\n",
    "       \n",
    "        final = 0\n",
    "        for i in range(n):\n",
    "            if matrix[i][0]>final:\n",
    "                final = 1\n",
    "        for j in range(m):\n",
    "            if matrix[0][j]>final:\n",
    "                final = 1\n",
    "\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,m):\n",
    "                \n",
    "                #如果自己是1\n",
    "                if matrix[i][j] == 1:\n",
    "                    \n",
    "                    #如果左上不是1\n",
    "                    if matrix_copy[i-1][j-1] == 0:\n",
    "                        matrix_copy[i][j] = 1\n",
    "                        if 1>final:\n",
    "                            final =1\n",
    "                    #如果左上是1\n",
    "                    else: \n",
    "                        \n",
    "                        #得到边长、检查上面和左面、赋值\n",
    "                        lenth = int(matrix_copy[i-1][j-1]**(1/2))\n",
    "                        res = 1\n",
    "                      \n",
    "                        for tmp in range(1,lenth+1):\n",
    "                            if matrix[i-tmp][j] == matrix[i][j-tmp] ==1:\n",
    "                                res+=1\n",
    "                            else:\n",
    "                                break\n",
    "                        tmp = res**2\n",
    "                        matrix_copy[i][j] = tmp\n",
    "                        if tmp>final:\n",
    "                            final = tmp\n",
    "                #如果自己不是1\n",
    "                else:\n",
    "                    matrix_copy[i][j] = 0\n",
    "\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        are = 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "        for i in range(1, n):\n",
    "            matrix[i][0] += matrix[i-1][0]\n",
    "        for j in range(1, m):\n",
    "            matrix[0][j] += matrix[0][j-1]\n",
    "        temp = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                matrix[i][j] += matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp[i+1][j+1] = matrix[i][j]\n",
    "        for l in range(min(m,n)-1, -1, -1):\n",
    "            for i in range(1, n-l+1):\n",
    "                for j in range(1, m-l+1):\n",
    "                    if temp[i+l][j+l] - temp[i+l][j-1] - temp[i-1][j+l] + temp[i-1][j-1] == (l+1)**2:\n",
    "                        are = max(are, (l+1)**2)\n",
    "                        return are\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        b=len(matrix)\n",
    "        a=len(matrix[0])\n",
    "        for i in range(a):\n",
    "            for j in range(b):\n",
    "                if i*j!=0 and int(matrix[j][i])==1:\n",
    "                    matrix[j][i]=1+min(int(matrix[j][i-1]),int(matrix[j-1][i-1]),int(matrix[j-1][i]))\n",
    "                else:\n",
    "                    matrix[j][i]=int(matrix[j][i])\n",
    "        return max([(matrix[j][i])**2 for i in range(a) for j in range(b)])\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        ans=int(matrix[0][0])\n",
    "        if len(matrix)*len(matrix[0])==1:\n",
    "            return ans\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                width=min(i,j)\n",
    "                if matrix[i][j]=='1' and   width>0 and matrix[i-1][j-1]>=1 and matrix[i-1][j]>=1 and matrix[i][j-1]>=1:\n",
    "                    matrix[i][j]=(pow(min(matrix[i-1][j-1],matrix[i][j-1],matrix[i-1][j]),0.5)+1)**2\n",
    "                else:\n",
    "                    matrix[i][j]=int(matrix[i][j])\n",
    "                ans=max(ans,int(matrix[i][j]))\n",
    "        return  ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        \n",
    "        # 初始化\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if matrix[i][0] == 1:\n",
    "                ans = 1\n",
    "                break\n",
    "        for j in range(m):\n",
    "            if matrix[0][j] == 1:\n",
    "                ans = 1\n",
    "                break\n",
    "        \n",
    "        # 填表\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] = (min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]) ** 0.5 + 1) ** 2\n",
    "                    ans = max(ans, matrix[i][j])\n",
    "        \n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        result = -1\n",
    "        # dp[i][j]代表以matrix[i][j]为右下角最大正方形面积\n",
    "        dp = matrix.copy()\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if i==0 or j==0 or not int(matrix[i][j]):\n",
    "                    result = max(result,int(matrix[i][j]))\n",
    "                    continue\n",
    "                size = int(math.sqrt(int(dp[i-1][j-1])))\n",
    "                k=0\n",
    "                while k<size:\n",
    "                    if int(matrix[i][j-k-1]) and int(matrix[i-k-1][j]):\n",
    "                        k+=1\n",
    "                    else:\n",
    "                        break\n",
    "                dp[i][j] = (k+1)**2\n",
    "                result = max(result,int(dp[i][j]))\n",
    "        print(dp)\n",
    "        return result\n",
    "\n",
    "\"\"\"\n",
    "0,0,0,1\n",
    "1,1,0,1\n",
    "1,1,1,1\n",
    "0,1,1,1\n",
    "0,1,1,1\n",
    "\"\"\"\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        result = -1\n",
    "        # dp[i][j]代表以matrix[i][j]为右下角最大正方形面积\n",
    "        dp = matrix.copy()\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if i==0 or j==0 or not int(matrix[i][j]):\n",
    "                    result = max(result,int(matrix[i][j]))\n",
    "                    continue\n",
    "                size = int(math.sqrt(int(dp[i-1][j-1])))\n",
    "                flag = True\n",
    "                k=0\n",
    "                while k<size:\n",
    "                    if int(matrix[i][j-k-1]) and int(matrix[i-k-1][j]):\n",
    "                        k+=1\n",
    "                    else:\n",
    "                        break\n",
    "                dp[i][j] = (k+1)**2 if flag and int(matrix[i][j]) else int(matrix[i][j])\n",
    "                result = max(result,int(dp[i][j]))\n",
    "        print(dp)\n",
    "        return result\n",
    "\n",
    "\"\"\"\n",
    "0,0,0,1\n",
    "1,1,0,1\n",
    "1,1,1,1\n",
    "0,1,1,1\n",
    "0,1,1,1\n",
    "\"\"\"\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        dp = [[0]*m for _ in range(n)]\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    if i == 0 or j == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1\n",
    "                    s = max(dp[i][j], s)\n",
    "        return s*s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [ [0]*n for _ in range(m)]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or j==0:\n",
    "                    dp[i][j] = int(matrix[i][j])\n",
    "                elif matrix[i][j] == \"0\":\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans**2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        dp = [[1 if matrix[0][_] == '1' else 0 for _ in range(len(matrix[0]))]]\n",
    "        maxi = 0\n",
    "        for t in range(1, len(matrix)):\n",
    "            dp.append([0]*len(matrix[0]))\n",
    "            if matrix[t][0] == '1':\n",
    "                dp[t][0] = 1\n",
    "                maxi = 1\n",
    "            else:\n",
    "                dp[t][0] = 0\n",
    "        if 1 in dp[0]: maxi = 1\n",
    "        for row in range(1, len(matrix)):\n",
    "            for col in range(1, len(matrix[0])):\n",
    "                if matrix[row][col] == '1':\n",
    "                    dp[row][col] = min(dp[row-1][col-1], dp[row][col-1], dp[row-1][col]) + 1\n",
    "                    maxi = max(dp[row][col]**2, maxi, 1)\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[-1]*n for _ in range(m)]\n",
    "        max_len = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    if matrix[i][j] == \"0\":\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = 1\n",
    "                        if dp[i][j] > max_len:\n",
    "                            max_len = dp[i][j]\n",
    "                else:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1\n",
    "                        if dp[i][j] > max_len:\n",
    "                            max_len = dp[i][j]\n",
    "                    else:\n",
    "                        dp[i][j] = 0\n",
    "        print(dp)\n",
    "        return max_len**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalSquare(self, matrix: List[List[str]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        max_square_side = 0\n",
    "\n",
    "        # 初始化第一行和第一列\n",
    "        for i in range(m):\n",
    "            dp[i][0] = int(matrix[i][0])\n",
    "            max_square_side = max(max_square_side, dp[i][0])\n",
    "        for j in range(n):\n",
    "            dp[0][j] = int(matrix[0][j])\n",
    "            max_square_side = max(max_square_side, dp[0][j])\n",
    "\n",
    "        # 动态规划填表\n",
    "        for row in range(1, m):\n",
    "            for col in range(1, n):\n",
    "                if matrix[row][col] == '1':\n",
    "                    dp[row][col] = min(dp[row-1][col], dp[row][col-1], dp[row-1][col-1]) + 1\n",
    "                    max_square_side = max(max_square_side, dp[row][col])\n",
    "\n",
    "        return max_square_side ** 2\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
